package com.xs.designpattern;

/**
 * @author xs
 */
public class TreeNode<T extends Comparable<T>> {
    private final T val;
    private TreeNode<T> left;
    private TreeNode<T> right;

    /**
     * 创建一个具有给定值和空子节点的 TreeNode
     *
     * @param val 给定节点的值
     */
    public TreeNode(T val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }

    public T getVal() {
        return val;
    }

    public TreeNode<T> getLeft() {
        return left;
    }

    private void setLeft(TreeNode<T> left) {
        this.left = left;
    }

    public TreeNode<T> getRight() {
        return right;
    }

    private void setRight(TreeNode<T> right) {
        this.right = right;
    }

    /**
     * 根据给定值将新的 TreeNode 插入到 self 表示的子树中
     *
     * @param valToInsert 作为新 TreeNode 插入的值
     */
    public void insert(T valToInsert) {
        TreeNode<T> parent = getParentNodeOfValueToBeInserted(valToInsert);
        parent.insertNewChild(valToInsert);
    }

    /**
     * 获取给定值的父树节点以插入到 BST 中
     *
     * @param valToInsert 要插入的新 TreeNode 的值
     * @return `valToInsert` 的父树节点
     */
    private TreeNode<T> getParentNodeOfValueToBeInserted(T valToInsert) {
        TreeNode<T> parent = null;
        TreeNode<T> curr = this;

        while (curr != null) {
            parent = curr;
            curr = curr.traverseOneLevelDown(valToInsert);
        }

        return parent;
    }

    /**
     * 根据要插入的值返回 self 的左子或右子；维护 BST 的完整性
     *
     * @param value 将插入到 self 下面的 TreeNode 的值
     * @return self 的子 TreeNode 表示将插入“value”的子树
     */
    private TreeNode<T> traverseOneLevelDown(T value) {
        if (this.isGreaterThan(value)) {
            return this.left;
        }
        return this.right;
    }

    /**
     * 向 self 添加一个给定值的新子 TreeNode。警告：此方法具有破坏性（将覆盖现有的树结构（如果有）），并且只能由此类的 insert() 方法调用。
     *
     * @param valToInsert Value of the new TreeNode to be inserted
     */
    private void insertNewChild(T valToInsert) {
        if (this.isLessThanOrEqualTo(valToInsert)) {
            this.setRight(new TreeNode<>(valToInsert));
        } else {
            this.setLeft(new TreeNode<>(valToInsert));
        }
    }

    private boolean isGreaterThan(T val) {
        return this.val.compareTo(val) > 0;
    }

    private boolean isLessThanOrEqualTo(T val) {
        return this.val.compareTo(val) < 1;
    }

    @Override
    public String toString() {
        return val.toString();
    }
}
